package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

class JianShengZiIiLcof {
    // 2022-09-05 12:44:38
    public static void main(String[] args) {
        Solution solution = new JianShengZiIiLcof().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int cuttingRope(int n) {
            if (n <= 3) return n - 1;
            /* 据 数学证明： 当 n >= 3时，因数 拆分成 3 的计算结果 较大
                当 n < 3时，因数越大，计算结果越大
            */
            int threadhold = 1000000007;
            long result = 1L;
            while (n > 4) {
                result = result * 3 % threadhold;
                n -= 3;
            } /* 将 最后一个 因数 计算在内 */
            result = result * n % threadhold;
            return (int) result;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}